package cn.edu.jxau.test;

import java.util.Arrays;

import cn.edu.jxau.util.LinkedStack;
import cn.edu.jxau.util.Stack;

public class DirectedCycle {

    public static void main(String[] args) {

        DirectedGraph g = new DirectedGraph(6);
        g.addEdge(0, 5);
        g.addEdge(5, 4);
        g.addEdge(4, 3);
        g.addEdge(3, 5);
        DirectedCycle dc = new DirectedCycle(g);
        if (dc.hasCycle()) {
            for (int i : dc.cycle()) {
                System.out.print(i + " ");
            }
        }
    }

    /**
     * 标记
     */
    private boolean[] marked;

    /**
     * 存储路径信息，用于构造环
     */
    private int[] edgeTo;

    /**
     * 如果有向图中存在环的话，cycle就会存储环的信息
     */
    private Stack<Integer> cycle;

    /**
     * 用于辅助检测有向图中是否有环
     */
    private boolean[] onStack;

    public DirectedCycle(DirectedGraph g) {

        marked = new boolean[g.v()];
        edgeTo = new int[g.v()];
        onStack = new boolean[g.v()];
        for (int v = 0; v < g.v(); v++) {
            if (!marked[v])
                dfs(g, v);
        }
    }

    private void dfs(DirectedGraph g, int v) {

        onStack[v] = true;
        marked[v] = true;
        for (int w : g.adj(v)) {
            if (cycle != null) { // 环已找到，直接return
                return;
            } else if (!marked[w]) {
                edgeTo[w] = v;
                dfs(g, w);
            } else if (onStack[w]) { // 环已找到，构造环
                cycle = new LinkedStack<>();
                for(int x=v;x!=w;x=edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
        onStack[v] = false;
    }

    public boolean hasCycle() {
        return cycle != null;
    }

    public Iterable<Integer> cycle() {
        return cycle;
    }
}
